/*
 * @Author: szx
 * @Date: 2022-03-10 15:13:57
 * @LastEditTime: 2022-03-10 15:19:18
 * @Description:
 * @FilePath: \leetcode\200-299\216\216_2.js
 */
/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function (k, n) {
    const res = [];
    const backtrack = (arr, sum, index) => {
        if (arr.length > k || sum > n) return;
        if (sum == n && arr.length == k) {
            if (sum == n) res.push(Array.from(arr));
            return;
        }
        for (let i = index; i <= 9 - (k - arr.length) + 1; i++) {
            arr.push(i);
            backtrack(arr, sum + i, i + 1);
            arr.pop();
        }
    };
    backtrack([], 0, 1);
    return res;
};
console.log(combinationSum3(3, 9));
